#include <linux/rbtree.h>
#include <linux/rbtree_augmented.h>

RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb,
                         struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size)

static void __link_va(struct vmap_area *va, struct rb_root *root,
                      struct rb_node *parent, struct rb_node **link,
                      struct list_head *head, bool augment)
{
    /*
     * VA is still not in the list, but we can
     * identify its future previous list_head node.
     */
    if (likely(parent))
    {
        head = &rb_entry(parent, struct vmap_area, rb_node)->list;
        if (&parent->rb_right != link)
            head = head->prev;
    }

    /* Insert to the rb-tree */
    rb_link_node(&va->rb_node, parent, link);
    if (augment)
    {
        /*
         * Some explanation here. Just perform simple insertion
         * to the tree. We do not set va->subtree_max_size to
         * its current size before calling rb_insert_augmented().
         * It is because we populate the tree from the bottom
         * to parent levels when the node _is_ in the tree.
         *
         * Therefore we set subtree_max_size to zero after insertion,
         * to let __augment_tree_propagate_from() puts everything to
         * the correct order later on.
         */
        rb_insert_augmented(&va->rb_node,
                            root, &free_vmap_area_rb_augment_cb);
        va->subtree_max_size = 0;
    }
    else
    {
        rb_insert_color(&va->rb_node, root);
    }

    /* Address-sort this list */
    list_add(&va->list, head);
}

static inline void link_va(struct vmap_area *va, struct rb_root *root,
                           struct rb_node *parent, struct rb_node **link,
                           struct list_head *head)
{
    __link_va(va, root, parent, link, head, false);
}

static inline void unlink_va(struct vmap_area *va, struct rb_root *root)
{
    // todo
}

/*
 * This function returns back addresses of parent node
 * and its left or right link for further processing.
 *
 * Otherwise NULL is returned. In that case all further
 * steps regarding inserting of conflicting overlap range
 * have to be declined and actually considered as a bug.
 */
static struct rb_node **find_va_links(struct vmap_area *va,
                                      struct rb_root *root, struct rb_node *from,
                                      struct rb_node **parent)
{
    struct vmap_area *tmp_va;
    struct rb_node **link;

    if (root)
    {
        link = &root->rb_node;
        if (unlikely(!*link))
        {
            *parent = NULL;
            return link;
        }
    }
    else
    {
        link = &from;
    }

    /*
     * Go to the bottom of the tree. When we hit the last point
     * we end up with parent rb_node and correct direction, i name
     * it link, where the new va->rb_node will be attached to.
     */
    do
    {
        tmp_va = rb_entry(*link, struct vmap_area, rb_node);

        /*
         * During the traversal we also do some sanity check.
         * Trigger the BUG() if there are sides(left/right)
         * or full overlaps.
         */
        if (va->va_end <= tmp_va->va_start)
            link = &(*link)->rb_left;
        else if (va->va_start >= tmp_va->va_end)
            link = &(*link)->rb_right;
        else
        {
            WARN(1, "vmalloc bug: 0x%lx-0x%lx overlaps with 0x%lx-0x%lx\n",
                 va->va_start, va->va_end, tmp_va->va_start, tmp_va->va_end);

            return NULL;
        }
    } while (*link);

    *parent = &tmp_va->rb_node;
    return link;
}
